import math
from typing import List


class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        left = 1
        right = sum(quantities)

        while left < right:
            mid = (left + right) // 2

            need = 0
            for q in quantities:
                need += math.ceil(q / mid)
                if need > n:
                    break

            if need <= n:  # 每个商店分mid是够的，可以尝试更少的mid
                right = mid
            else:  # 每个商店分mid是不够的，需要更多的mid
                left = mid + 1

        return right


if __name__ == "__main__":
    print(Solution().minimizedMaximum(n=6, quantities=[11, 6]))  # 3
    print(Solution().minimizedMaximum(n=7, quantities=[15, 10, 10]))  # 5
    print(Solution().minimizedMaximum(n=1, quantities=[100000]))  # 100000
